package org.example;

public class Main {
    public static void main(String[] args) {
        System.out.println("Hello world!");
    }
}
//493.翻转对
class Solution {
    int[] tmp;
    public int reversePairs(int[] nums) {
        tmp = new int[nums.length];
        return mergeSort(nums, 0, nums.length - 1);
    }

    private int mergeSort(int[] nums, int l, int r) {
        if(l >= r) return 0;

        //根据中点划分区间
        int mid = (l + r) >> 1;
        int ret = 0;
        ret += mergeSort(nums, l, mid);
        ret += mergeSort(nums, mid + 1, r);

        //在两个区间为降序的情况之下, 计算指向右区间的元素后面有多少元素的两倍比指向左区间的元素小
        int cur1 = l, cur2 = mid + 1;
        while(cur1 <= mid && cur2 <= r){
            while(cur2 <= r && nums[cur1] <= (long)nums[cur2] * 2){
                cur2++;
            }
            if(nums[cur1] > (long)nums[cur2] * 2){
                ret += r - cur2 + 1;
            }
            cur1++;
        }

        //合并两个有序数组
        cur1 = l;
        cur2 = mid + 1;
        int i = 0;
        while(cur1 <= mid && cur2 <= r){
            if(nums[cur1] > nums[cur2]){
                tmp[i++] = nums[cur1++];
            }else{
                tmp[i++] = nums[cur2++];
            }
        }
        //处理剩余的区间元素
        while(cur1 <= mid)   tmp[i++] = nums[cur1++];
        while(cur2 <= r)  tmp[i++] = nums[cur2++];

        for(int k = l; k <= r; k++){
            nums[k] = tmp[k - l];
        }
        return ret;
    }
}